import java.util.Arrays;

public class CountSort {
   public static void countingSort(int[] arr){
       if (arr.length<=1)
           return;
       int min=arr[0],max=arr[0];

       for (int n : arr) {//找出最大最小值
           if (n < min)
               min = n;
           if (n > max)
               max = n;
       }

       int[] bucket=new int[max-min+1];
       Arrays.fill(bucket,0);

       for (int n : arr) //根据每个数字出现次数分配
           bucket[n - min]++;

       int index=0;
       for(int i=0;i<bucket.length;i++){//根据计数数组重新分配原数组
           int count=bucket[i];
           while (count>0){
               arr[index++]=i+min;
               count--;
           }
       }
   }
}
